package 中等.树;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一
 * 个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 
 * other(其他)，可以形成新的单词 another(另一个)。
 * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子
 * sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成
 * 它的词根，则用最短的词根替换它。
 * 你需要输出替换之后的句子。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/replace-words
 */
public class 单词替换_648 {

    public static void main(String[] args) {

        List<String> dictionary = new ArrayList<>();
        dictionary.add("cat");
        dictionary.add("bat");
        dictionary.add("rat");

        System.out.println(replaceWords2(dictionary, "the cattle was rattled by the battery"));

    }

    /**
     * 词根永远是单词的前缀
     * 哈希存储前缀
     *
     * @param dictionary
     * @param sentence
     * @return
     */
    public static String replaceWords(List<String> dictionary, String sentence) {
        Set<String> diction = new HashSet<>(dictionary);
        StringBuilder stringBuilder = new StringBuilder();

        int left = 0;
        while (left < sentence.length()) {
            int right = left;
            while (right < sentence.length() && sentence.charAt(right) != ' ') right++;

            boolean flag = true;
            for (int curRight = left + 1; curRight <= right; curRight++) {
                String root = sentence.substring(left, curRight);
                if (diction.contains(root)) {
                    stringBuilder.append(root)
                            .append(" ");
                    flag = false;
                    break;
                }
            }
            if (flag) {
                stringBuilder.append(sentence.substring(left, right))
                        .append(" ");
            }
            left = right + 1;
        }
        return stringBuilder.toString().trim();
    }

    /**
     * 字典树
     * 将词根存入字典数，并且标记词根末尾字符
     *
     * @param dictionary
     * @param sentence
     * @return
     */
    public static String replaceWords2(List<String> dictionary, String sentence) {
        StringBuilder stringBuilder = new StringBuilder();
        Tree tree = new Tree();
        for (String diction : dictionary) {
            tree.insert(diction);
        }

        int left = 0;
        while (left < sentence.length()) {
            int right = left;
            while (right < sentence.length() && sentence.charAt(right) != ' ') right++;
            stringBuilder.append(tree.findMinPrefix(sentence.substring(left, right)))
                    .append(" ");
            left = right + 1;
        }

        return stringBuilder.toString().trim();
    }

    static class Tree {

        private boolean end;

        private Tree[] children = new Tree[26];

        public void insert(String str) {
            Tree curNode = this;
            for (int i = 0; i < str.length(); i++) {
                int curChar = str.charAt(i) - 'a';
                if (curNode.children[curChar] == null) {
                    curNode.children[curChar] = new Tree();
                }
                curNode = curNode.children[curChar];
            }
            curNode.end = true;
        }

        // 最短前缀
        public String findMinPrefix(String str) {
            Tree curNode = this;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                stringBuilder.append(str.charAt(i));
                int index = str.charAt(i) - 'a';
                if (curNode.children[index] == null) return str;
                if (curNode.children[index].end) {
                    return stringBuilder.toString();
                }
                curNode = curNode.children[index];
            }
            return stringBuilder.toString();
        }
    }

}
